#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right){} 
};
class Solution1
{
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> ret;
        TreeNode *cur = root;
        TreeNode *prev = nullptr;
        stack<TreeNode *> s;
        while (cur || !s.empty())
        {
            while (cur != nullptr)
            {
                s.push(cur);
                cur = cur->left;
            }
            //出栈说明左子树已经访问过了
            TreeNode *top = s.top();
            //记录上一个访问的结点，当右子树为空或者上一个访问的结点为右子树的根节点时则说明右子树已经访问过了，可以直接pop掉
            if (top->right == nullptr || top->right == prev)
            {
                ret.push_back(top->val);
                prev = top;
                s.pop();
            }
            else
            {
                cur = top->right;
            }
        }
        return ret;
    }
};

class Solution2
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        TreeNode *cur = root;
        vector<int> ret;
        stack<TreeNode *> s;
        while (cur != nullptr || !s.empty())
        {
            while (cur)
            {
                ret.push_back(cur->val);
                s.push(cur);
                cur = cur->left;
            }
            TreeNode *top = s.top();
            s.pop();
            cur = top->right;
        }
        return ret;
    }
};
class Solution3
{
public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> ret;
        TreeNode *cur = root;
        stack<TreeNode *> s;
        while (cur || !s.empty())
        {
            while (cur != nullptr)
            {
                s.push(cur);
                cur = cur->left;
            }
            TreeNode *top = s.top();
            s.pop();
            ret.push_back(top->val);
            cur = top->right;
        }
        return ret;
    }
};
int main()
{
    return 0;
}